package com.company.tree;

import com.sun.org.apache.regexp.internal.REUtil;
import org.junit.Test;

import javax.jws.Oneway;
import javax.lang.model.util.ElementScanner6;
import javax.management.remote.rmi._RMIConnection_Stub;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @description:
 * @author: Code-zyc
 * @date: Created in 2021/12/7 21:42
 * @version: 1.0
 * @modified By:
 */
public class TestTree {

    @Test
    public void  test(){
//        TreeNode one=new TreeNode(1);
//        TreeNode two2=new TreeNode(2);
//        TreeNode two1=new TreeNode(2);
//
//        one.left=two1;
//        one.right=two2;
//        two1.right=new TreeNode(3);
//        two2.right=new TreeNode(3);
//
//        System.out.println(isSymmetric(one));
        Node one=new Node(1);
        Node two=new Node(2);
        Node three =new Node(3);
        one.left=two;
        one.right=three;
        connect(one);


    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }



    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }


    /**二叉树的最近公共祖先
     给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

     百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

     作者：力扣 (LeetCode)
     链接：https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xopaih/
     来源：力扣（LeetCode）
     著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * **/
    //参考自评论区 大佬
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root==p||root==q){
            return root;
        }
        if (root!=null){
            TreeNode lnode = lowestCommonAncestor(root.left, p, q);
            TreeNode rnode = lowestCommonAncestor(root.right, p, q);
            if (lnode!=null&&rnode!=null){
                //这表示 左右找到
                return root;
            }else if(lnode==null){
                return rnode;
            }else {
                return lnode;
            }
        }
        return  null;
    }

    /**填充每个节点的下一个右侧节点指针 II
     给定一个二叉树**/

    public Node connect(Node root) {
        //创建一个 临时的节点
        Node temple=new Node();
        Node up=root; //创建在上面游走的节点
        Node down=temple; //创建一个 在下面一层游走的节点
        while (up!=null){

            if (up.left!=null){ //
                //上面的左边不为0 进行链接
              down.next=up.left;
                //移动down
                down=down.next;
            }
            if (up.right!=null){
                down.next=up.right;
                //移动down
                down=down.next;
            }

            //在移动  up
            if (up.next==null){
                //这个表示 这一层遍历完了
                //up下移动
                up=temple.next;
                //temple  重新建立
                temple=new Node();
                //down 也重新建立
                down=temple;
            }else {
                up=up.next;
            }
        }
        return root;
    }

    /**填充每个节点的下一个右侧节点指针
     给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下
     * **/
    public Node connect2(Node root) {
        //思路 就是层序遍历 然后 那一层进行 链接即可
        if (root==null){
            return root;
        }
        Node temple=root;
        Queue<Node> queue=new LinkedList<>();
        queue.add(temple);
        while (!queue.isEmpty()){
            //取出一层 进行链接
            Queue<Node> templeQueue=new LinkedList<>();
            while (!queue.isEmpty()){
                Node node = queue.poll();
                templeQueue.add(node);
                node.next=queue.peek();
            }

            //把每一层的左右放进去
            while (!templeQueue.isEmpty()){
                Node node = templeQueue.poll();
                if (node.left!=null){
                    queue.add(node.left);

                }
                if (node.right!=null){
                    queue.add(node.right);
                }




            }
        }
        return  root;
    }




  /**
         * 从中序与后序遍历序列构造二叉树
         * 根据一棵树的中序遍历与后序遍历构造二叉树。*/

//  public TreeNode buildTree(int[] inorder, int[] postorder) {
//
//  }

        /**
   * 路径总和
   * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
   *
   * 叶子节点 是指没有子节点的节点。
   *
   * 作者：力扣 (LeetCode)
   * 链接：https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xo566j/
   * 来源：力扣（LeetCode）
   * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
        public boolean hasPathSum(TreeNode root, int targetSum) {
            if (root==null){ //递归结束的条件
                return false;
            }
            if (root.val==targetSum && root.left==null && root.right==null){
                //就这有这种情况才可能返回true
                return true;
            }else {
                return   hasPathSum(root.left,targetSum-root.val) ||
                        hasPathSum(root.right,targetSum-root.val);
            }
        }



     /**
   * 对称二叉树
   * 给定一个二叉树，检查它是否是镜像对称的。*/

     public boolean isSymmetric(TreeNode root) {

            if (root==null){
                return true;
            }
         return    isSymmetricDiGui(root.left,root.right);
     }
     public boolean isSymmetricDiGui(TreeNode node1,TreeNode node2){
        if (node1==null && node2==null){
            return true;
        }
        if (node1==null || node2==null){
            return false;
        }
         if (  node1.val == node2.val){
             return isSymmetricDiGui(node1.left,node2.right) && isSymmetricDiGui(node1.right,node2.left);
         }else {
             return false;
         }

     }

    /**二叉树的最大深度
     给定一个二叉树，找出其最大深度。

     二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

     说明: 叶子节点是指没有子节点的节点。
     * */
    public int maxDepth(TreeNode root) {
        if (root==null){
            return 0;
        }

       return Math.max((maxDepth(root.left)+1), (1+maxDepth(root.right)));
    }

    /**二叉树的层序遍历
     给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
     * */
    public List<List<Integer>> levelOrder(TreeNode root) {

        Queue<TreeNode> queue=new LinkedList();
        List<List<Integer>> result=new ArrayList<>();
        if (root==null){
            return result;
        }
        queue.add(root);
        while (!queue.isEmpty()){
            //把这一层的添加进去
            List<TreeNode> nodes=new ArrayList<>();  //记录一个层次的node
           while (!queue.isEmpty()){
              nodes.add( queue.poll());
           }
           //然后依次循环 遍历取出值 放进结果 左右节点放进队列
            List<Integer> integers=new ArrayList<>();
            for (int i = 0; i < nodes.size(); i++) {
                TreeNode treeNode = nodes.get(i);
                integers.add(treeNode.val);
                if (treeNode.left!=null){
                    queue.add(treeNode.left);
                }
                if (treeNode.right!=null){
                    queue.add(treeNode.right);
                }

            }
            result.add(integers);
        }

        return  result;
    }


    /**二叉树的后序遍历
     给定一个二叉树，返回它的 后序 遍历
     * */
    List<Integer> resultForpostorderTraversal;
    public List<Integer> postorderTraversal(TreeNode root) {
        resultForpostorderTraversal=new ArrayList<>();
        postorderTraversalDiGui(root);
        return resultForpostorderTraversal;
    }

    private void postorderTraversalDiGui(TreeNode root) {
        if (root==null){
            return;
        }
        postorderTraversalDiGui(root.left);
        postorderTraversalDiGui(root.right);
        resultForpostorderTraversal.add(root.val);
    }

    /**二叉树的中序遍历

     * */

    List<Integer> resultForinorderTraversal;
    public List<Integer> inorderTraversal(TreeNode root) {
        resultForinorderTraversal=new ArrayList<>();
        inorderTraversalDiGui(root);
        return resultForinorderTraversal;
    }

    private void inorderTraversalDiGui(TreeNode root) {
        if (root==null){
            return;
        }
        inorderTraversalDiGui(root.left);
        resultForinorderTraversal.add(root.val);
        inorderTraversalDiGui(root.right);
    }
    /**二叉树的前序遍历
     给你二叉树的根节点 root ，返回它节点值的 前序 遍历。


     * */

    List<Integer> resultForpreorderTraversal;

    public List<Integer> preorderTraversal(TreeNode root) {
        resultForpreorderTraversal=new ArrayList<>();
        preorderTraversalDiGui(root);
        return resultForpreorderTraversal;
    }

    private void preorderTraversalDiGui(TreeNode root) {
        if (root==null){
            return;
        }
        resultForpreorderTraversal.add(root.val);
        preorderTraversalDiGui(root.left);
        preorderTraversalDiGui(root.right);
    }


}
